МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління / Лабораторна робота №3-4 з дисципліни “Математичні методи дослідження операцій” на тему «Симплекс метод »  Мета роботи: вивчення симплекс методу для знаходження розв’язку задач лінійного програмування . План Короткі теоретичні відомості. Постановка задачі Симплекс метод розв’язаний за допомогою симплекс таблиць Жордана Гауса Симплекс метод розв’язаний за допомогою симлекс таблиць з додаванням змінних. Розв’язання за допомогою пакету програм SimplexWin Розв’язання за допомогою власної програми. Хід роботи 1. Короткі теоретичні відомості Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь або нерівностей і лінійного функціоналу. Для приведення системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис. I. Обмеження виду «» - ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, ліворуч - те що отримуємо. При таких обмеженнях вводять додаткові змінні з коефіцієнтом «+1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0». II. Обмеження виду «=». Часто буває, що незважаючи на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. В цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. В систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», що прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»). III. Обмеження виду «» - планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку. Алгоритм симплекс методу Нехай система приведена до канонічного виду. X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 (1) X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 ………………………………………………………………. Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm У ній m базисних змінних, k вільних змінних. m + k = n - всього змінних. Fmin = C1X1 + C2X2 + C3X3 + .... + CnXn Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці в якості допустимого рішення приймаємо всі Xj = 0 (j = m +1, m +2, ..., m + k). При цьому всі базисні змінні Xi = Hi. Для подальших міркувань обчислень будемо користуватися першою симплекс таблицею. Таблица 1 –Перша симплес таблиця . C Б H C1 C2 … Cm  Cm+1 … Cm+k     X1 X2 … Xm Xm+1 … Xm+k   C1 C2 C3 : : Cm  X1 X2 X3 : : Xm  h1 h2 h3 : : hm 1 0 0 : : 0 0 1 0 : : 0 : : : : : : 0 0 0 : : 0 q1,m+1 q2,m+1 q3,m+1 : : qm,m+1 : : : : : : q1,m+k q2,m+k q3,m+k : : qm,m+k   F= F0   … m m+1 … m+k   Перший стовпчик-коефіцієнти в цільової функції при базисних змінних. Другий стовпчик - базисні змінні. Третій стовпчик - вільні члени (hi0). Самий верхній рядок - коефіцієнти при цільовій функції. Другий верхній рядок - змінні, що входять в цільову функцію і в систему обмежень. Основне поле симплекс методу - система коефіцієнтів з рівняння. Останній рядок - служить для того, щоб відповісти на питання: «оптимальний план чи ні». 2. Постановка задачі Розв’язати задачу лінійного програмування симплекс методом (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100) Варіант 48 F(x1,x2) = 3x1 + 6x2
max ; x1 + x2
8, 3x1 + 7x2
21, x1 + 2x2
6, 0
x1
7, 0
x2
7. 2.1 Розв’язання без використання пакетів програм. Cимплекс метод розв’язаний за допомогою сиплекс таблиць Жордана -Гауса. Для того щоб показати , що я освоїв даний матеріал зміню напрям цільової функції на min . Оскільки в даній лабораторній роботі розглядається і сиплекс метод двійної задачі то в наступному методі буде показано зн...